//
//  main.c
//  003--每日温度
//
//  Created by Shawn Li on 2020/5/12.
//  Copyright © 2020 Shawn. All rights reserved.
//

/*

LeetCode:
题目: 根据每日气温列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置0来代替。例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
解题关键:
*/

#include <stdio.h>
#include <stdlib.h>


void dailyTemperatures(int *data, int size, int *result, int *resSize){
    *result = (int)malloc(sizeof(int) * size);
    
//    注意此处是使用了栈思想，不需要真的实现一个堆栈
//    使用堆栈记录 data 的下标
    int *stack = malloc(sizeof(int) * size);
    *resSize = size;

    int top = 0;
    int tIndex;
    
//    初始化结果搜赋值为 0 其中最后一位到最后也是为 0。
    for (int i = 0; i < size; i++) {
        result[i]  = 0;
    }
    
    for (int i = 0; i < size; i++) {
//        若某一天温度大于栈顶元素了，那么即为温度升高了，所求天数则为下标之差。然后还需要看一下当前温度是不是比新的栈顶高。
        while (top > 0 && data[i] > data[stack[top - 1]]) {
            printf("栈顶 %2d \n", top);
            
            tIndex = stack[top - 1];
            result[tIndex] = i - tIndex;
            top--;
        }
//        直到栈为空或者说当前温度没有栈顶高，那么这个温度就是一个较低的温度他需要入栈等下一次升温再出栈
        stack[top] = i;
        top++;
    }
    
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    
    int testData[] = {10, 7, 8, 6, 5, 6, 7, 8, 9};
    int result[] = {};
    int resSize;
    
    printf("\n");
    dailyTemperatures(testData, 9, result, &resSize);
    
    for (int i = 0; i < 9; i++) {
        printf("%d ", testData[i]);
    }
    printf("\n");
    for (int i = 0; i < resSize; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");
    return 0;
}
